package com.hyper_yang.algorithmRecord.backTrack;

import java.util.*;

// 8皇后问题
public class EightQueens {
    // 在一个 8*8的棋盘上，放 8个皇后，有多少种放法。

    // 方法一: 暴力枚举 O(n^n * N^2)
    public List<int[]> eightQueens1() {
        // 定义保存结果的集合
        ArrayList<int[]> result = new ArrayList<>();
        // 用一个 int[8]保存一组解
        int[] solution = new int[8];
        // 遍历每种可以摆放的场景，判断是否符合题目限制
        for (solution[0] = 0; solution[0] < 8; solution[0]++) {
            for (solution[1] = 0; solution[1] < 8; solution[1]++) {
                for (solution[2] = 0; solution[2] < 8; solution[2]++) {
                    for (solution[3] = 0; solution[3] < 8; solution[3]++) {
                        for (solution[4] = 0; solution[4] < 8; solution[4]++) {
                            for (solution[5] = 0; solution[5] < 8; solution[5]++) {
                                for (solution[6] = 0; solution[6] < 8; solution[6]++) {
                                    for (solution[7] = 0; solution[7] < 8; solution[7]++) {
                                        if (check(solution)) {
                                            result.add(Arrays.copyOf(solution, 8)); // 直接 add的话保存的是索引
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        return result;
    }

    // 定义检查方法:
    public boolean check(int[] arr) { // 索引是行号，值是列号   // 任意两个皇后进行比较
        for (int i = 0; i < 7; i++) { // 第一个皇后
            for (int j = i + 1; j < 8; j++) { // 第二个皇后
                // 判断不能在同行、同列、同对角线【行列索引差不能相等】
                if (arr[i] == arr[j] || Math.abs(arr[i] - arr[j]) == Math.abs(i - j)) {
                    return false;
                }
            }
        }
        return true;
    }
// ===========================================================================================================

    // 方法二: 回溯法 O(n!)
    // 需要判断列不重复
    HashSet<Integer> cols = new HashSet<>();
    // 需要判断正对线不重复
    HashSet<Integer> diags1 = new HashSet<>();
    // 需要判断逆对角线不重复
    HashSet<Integer> diags2 = new HashSet<>();
    public List<int[]> eightQueens() {
        ArrayList<int[]> result = new ArrayList<>();
        int[] solution = new int[8];
        // 先对 solution做初始填充,表示未填充皇后的初始状态
        Arrays.fill(solution, -1);
        // 定义回溯方法，递归调用
        backtrack(result, solution, 0);
        return result;
    }

    // 实现回溯方法:
    private void backtrack(ArrayList<int[]> result, int[] solution, int row) {
        // 首先处理递归调用结束场景
        if (row >= 8) {
            result.add(Arrays.copyOf(solution, 8));
        } else {
            // 对于当前行，考察可能的皇后的位置，遍历每一列
            for (int column = 0; column < 8; column++) {
                // 1.是否冲突，冲突直接跳过，寻找下一位置
                // 1.1 判断同一列
                if (cols.contains(column)) continue;
                // 1.2 判断两条斜线
                int diag1 = row - column;
                int diag2 = row + column;
                if (diags1.contains(diag1)) continue;
                if (diags2.contains(diag2)) continue;

                // 2.如果不冲突，当前位置就放置皇后
                solution[row] = column;
                cols.add(column);
                diags1.add(diag1);
                diags2.add(diag2);

                // 3.递归调用，深度搜索下一行
                backtrack(result, solution, row + 1);

                // 4.回溯，将状态回滚，继续遍历当前行皇后可能的位置
                solution[row] = -1;
                cols.remove(column);
                diags1.remove(diag1);
                diags2.remove(diag2);
            }
        }
    }

    public static void main(String[] args) {
        EightQueens eightQueens = new EightQueens();
        for (int[] solution : eightQueens.eightQueens()) {
            PrintQueens(solution);
            System.out.println("=====================================");
        }
        System.out.println("一共有: " + eightQueens.eightQueens().size() + "种不同的的摆法");
    }
    // 打印方法，直观显示结果
    public static void PrintQueens(int[] queens) {
        int n = queens.length;
        for (int i = 0; i < n; i++) {
            String[] line = new String[n];
            Arrays.fill(line, "□");
            line[queens[i]] = "♕";
            for (String str : line)
                System.out.print(str + "\t");
            System.out.println();
        }
    }
}
